package m202405.d12;

import java.util.HashMap;
import java.util.Map;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/12 17:55
 */
public class Q138 {

    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node newHead = new Node(-1);
        Node p = head;
        Node np = newHead;
        while (p != null) {
            Node newNode = new Node(p.val);
            newNode.random = p.random;
            np.next = newNode;
            map.put(p, newNode);
            p = p.next;
            np = np.next;
        }
        newHead = newHead.next;
        np = newHead;
        while (np != null) {
            np.random = map.get(np.random);
            np = np.next;
        }
        return newHead;
    }

    public Node copyRandomList1(Node head) {
        Map<Node, Integer> map = new HashMap<>();
        Node p = head;
        int i = 0;
        while (p != null) {
            map.put(p, i);
            i++;
            p = p.next;
        }
        Node[] array = new Node[i];
        Node newHead = new Node(-1);
        p = head;
        i = 0;
        Node np = newHead;
        while (p != null) {
            np.next = new Node(p.val);
            array[i] = np.next;
            i++;
            np = np.next;
            p = p.next;
        }
        p = head;
        np = newHead.next;
        while (p != null) {
            Integer index = map.get(p.random);
            if (index != null) {
                np.random = array[index];
            }
            p = p.next;
            np = np.next;
        }
        return newHead.next;
    }

    private static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
